import java.util.Arrays;
import java.util.Comparator;
import java.util.Objects;
import java.util.PriorityQueue;

/**
 * Created by xiebang
 * Description
 * User:小谢
 * Date:2021-10-12
 * Time:20:24
 */

class Card1{
    public int rank;
    public String suit;
    public Card1(int rank,String suit){
        this.rank = rank;
        this.suit = suit;
    }

}
class Card implements Comparable<Card> {
    public int rank; // 数值
    public String suit; // 花色
    public Card(int rank, String suit) {
        this.rank = rank;
        this.suit = suit;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;//为null或者类型不同
        Card card = (Card) o;
        return rank == card.rank &&
                Objects.equals(suit, card.suit);
    }//比较是否相等，而不是大小关系

    @Override
    public int compareTo(Card o) {
        return this.rank - o.rank;
    }
}
//自定义对象的比较需要实现comparrable 或者comparator
//队列不能存储null

class Student{
    public int age;
    public int score;
    public Student(int age,int score){
        this.age = age;
        this.score = score;
    }

    @Override
    public String toString() {
        return "Student{" +
                "age=" + age +
                ", score=" + score +
                '}';
    }
}

class AgeComparator implements Comparator<Student> {
    @Override
    public int compare(Student o1, Student o2) {
        //return o1.age - o2.age;//小堆
        return o2.age - o1.age;//大堆
    }
}
class ScoreComparator implements Comparator<Student>{
    @Override
    public int compare(Student o1, Student o2) {
//        return o1.score - o2.score;
        return o2.score - o1.score;
    }
}
//对象之间的比较
public class TestDeno {
    public static void main8(String[] args) {
        AgeComparator ageComparator = new AgeComparator();
        ScoreComparator scoreComparator = new ScoreComparator();
        PriorityQueue<Student> priorityQueue = new PriorityQueue<>(scoreComparator);
        Student student = new Student(1,89);
        Student student1 = new Student(2,29);
        priorityQueue.offer(student);
        priorityQueue.offer(student1);
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());

    }
    public static void main7(String[] args) {
        Student student = new Student(1,89);
        Student student1 = new Student(2,29);
        AgeComparator ageComparator = new AgeComparator();
        System.out.println(ageComparator.compare(student, student1));
        ScoreComparator scoreComparator = new ScoreComparator();
        System.out.println(scoreComparator.compare(student, student1));

    }
    public static void main6(String[] args) {
        Card c1 = new Card(1,"♠");
        Card c2 = new Card(1,"♠");
        Card c3 = c1;

        //判断是否相等有equas方法
        System.out.println(c1.equals(c3));
        System.out.println(c1.equals(c2));

    }

    public static void main5(String[] args) {
        PriorityQueue<Card1> queue = new PriorityQueue<>();
        queue.offer(new Card1(1,"♥"));
        queue.offer(new Card1(2,"♥"));
    }

    public static void main4(String[] args) {
        TestHeap2 testHeap2 = new TestHeap2();
        int[] array = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};
        testHeap2.crateBigHeap(array);
        testHeap2.push(1);
        testHeap2.heapSort();
        testHeap2.show();
    }
    public static int[] topK(int[] array, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });
        for (int i = 0; i < array.length; i++) {
            if (minHeap.size() < k) {
                minHeap.offer(array[i]);
            } else {
                int top = minHeap.peek();
                if (top < array[i]) {
                    minHeap.poll();
                    minHeap.offer(array[i]);
                }
            }
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }
        return ret;
    }
    public static int[] topK2(int[] array, int k) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int i = 0; i < array.length; i++) {
            if (maxHeap.size() < k) {
                maxHeap.offer(array[i]);
            } else {
                int top = maxHeap.peek();
                if (top > array[i]) {
                    maxHeap.poll();
                    maxHeap.offer(array[i]);
                }
            }
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = maxHeap.poll();
        }
        return ret;
    }

    public static void main3(String[] args) {
        int[] array = {10, 8, 100, 78, 126, 30};
        int[] ret = topK(array, 3);
        System.out.println(Arrays.toString(ret));
        int[]  tmp = topK2(array,3);
        System.out.println(Arrays.toString(tmp));
    }

    public static void main2(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        //底层的大堆还是小堆
        priorityQueue.offer(10);
        priorityQueue.offer(1);
        priorityQueue.offer(-1);
        System.out.println(priorityQueue.poll());//-1
        System.out.println(priorityQueue.poll());//1
        System.out.println(priorityQueue.poll());//10
        //所以默认是小堆
    }

    public static void main1(String[] args) {
        TestHeap testHeap = new TestHeap();
        int[] array = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};
        testHeap.crateBigHeap(array);
        //testHeap.push(80);
        testHeap.poll();
    }
}

